package cn.zyl.demo.java.sort;

import cn.zyl.demo.common.tools.ArrayTool;
import cn.zyl.demo.common.tools.DateTool;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * AbstractArraySortSimple 抽象类说明: 排序抽象接口
 * <p>
 *     参考网址：</br>
 *     <a href="https://www.geekxh.com"> 小浩算法</a></br>
 *     <a href="https://www.cnblogs.com/gaochundong/p/complexity_of_algorithms.html">算法复杂度分析</a></br>
 *     <a href="https://jasonkayzk.github.io/">几种常见排序方法的优化</a></br>
 * </p>
 * <p>
 *     线性时间（非比较类排序）：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下届，以线性时间运行</br>
 *     非线性时间（比较类排序）：</br>
 *     最坏情况（Worst Case）：任意输入规模的最大运行时间。（Usually）</br>
 *     平均情况（Average Case）：任意输入规模的期待运行时间。（Sometimes）</br>
 *     最佳情况（Best Case）：通常最佳情况不会出现。（Bogus）</br>
 *     稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面。</br>
 *     不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面
 * </p>
 * -----------------------------------------------------------------------------------------------------
 * <table border="2" bgColor="gray" >
 *   <tr><th>排序算法名称|</th><th>是否线性时间|</th><th>时间复杂度-平均|</th><th>时间复杂度-最好|</th><th>时间复杂度-最坏|</th><th>空间复杂度|</th><th>稳定性</th></tr>
 *   <tr><td>插入</td><td>非线性</td><td>O(n²),O(n^2)</td><td>O(n²)</td><td>O(n)</td><td>O(1)</td><td>稳定</td></tr>
 *   <tr><td>希尔</td><td>非线性</td><td>O(n^1.3)</td><td>O(n²)</td><td>O(n)</td><td>O(1)</td><td>不稳定</td></tr>
 *   <tr><td>选择</td><td>非线性</td><td>O(n²)</td><td>O(n²)</td><td>O(n²)</td><td>O(1)</td><td>不稳定</td></tr>
 *   <tr><td>堆</td><td>非线性</td><td>O(n㏒₂n)</td><td>O(n㏒₂n)</td><td>O(n㏒₂n)</td><td>O(1)</td><td>不稳定</td></tr>
 *   <tr><td>冒泡</td><td>非线性</td><td>O(n²)</td><td>O(n²)</td><td>O(n)</td><td>O(1)</td><td>稳定</td></tr>
 *   <tr><td>快速</td><td>非线性</td><td>O(n㏒₂n)</td><td>O(n²)</td><td>O(n㏒₂n)</td><td>O(n㏒₂n)</td><td>不稳定</td></tr>
 *   <tr><td>归并</td><td>非线性</td><td>O(n㏒₂n)</td><td>O(n㏒₂n)</td><td>O(n㏒₂n)</td><td>O(n)</td><td>稳定</td></tr>
 *   <tr><td>计数</td><td>线性</td><td>O(n+k)</td><td>O(n+k)</td><td>O(n+k)</td><td>O(n+k)</td><td>稳定</td></tr>
 *   <tr><td>桶</td><td>线性</td><td>O(n+k)</td><td>O(n²)</td><td>O(n)</td><td>O(n+k)</td><td>稳定</td></tr>
 *   <tr><td>基数</td><td>线性</td><td>O(n*k)</td><td>O(n*k)</td><td>O(n*k)</td><td>O(n+k)</td><td>稳定</td></tr>
 * </table>
 * *******复杂度说明( log₂8 = 3, 2³=8 ; 2^3 = 8 )
 * <table border="2" bgColor="gray" >
 *   <tr><th>复杂度|</th><th>标记符号|</th><th>描述|</th></tr>
 *   <tr><td>常量(constant)</td><td>O(1)</td><td>操作的数量为常数，与输入的数据的规模无关。n = 1,000,000 -> 1-2 operations</td></tr>
 *   <tr><td>对数(logarithmic)</td><td>O(㏒₂n);O(㏒2n)</td><td>操作的数量与输入数据的规模 n 的比例是 log2 (n)。n = 1,000,000 -> 30 operations</td></tr>
 *   <tr><td>线性(linear)</td><td>O(n)</td><td>操作的数量与输入数据的规模 n 成正比。n = 10,000 -> 5000 operations</td></tr>
 *   <tr><td>平方(quadratic)</td><td>O(n²);O(n^2)</td><td>操作的数量与输入数据的规模 n 的比例为二次方。n = 500 -> 250,000 operations</td></tr>
 *   <tr><td>立方(cubic)</td><td>O(n³);O(n^3)</td><td>操作的数量与输入数据的规模 n 的比例为三次方。n = 200 -> 8,000,000 operations</td></tr>
 *   <tr><td>指数(exponential)</td><td>O(2^n),O(k^n),O(n!)</td><td>指数级的操作，快速的增长。n = 20 -> 1048576 operations</td></tr>
 * </table>
 * 性能 快>慢：O(1) > O(㏒₂n) > O(n) > O(n㏒₂n) > O(n²) > O(n³) > O(2^n) > O(n!) >O(n^n)
 * @author wsz
 * @version v1.0
 * @date 2020-08-13
 */
public abstract class AbstractArraySortSimple {
    /** 随机数对象常量 */
    protected static final Random RANDOM = new Random();
    /** 使用原子类int，统计算法迭代次数*/
    protected static AtomicInteger count ;
    /** 统计运行时间*/
    private static long startTime;
    protected static final int NE_1 = -1;
    protected static final int N_0 = 0;
    protected static final int N_1 = 1;
    protected static final int N_2 = 2;
    protected static final int N_3 = 3;
    protected static final int N_10 = 10;
    /**
     * 排序接口
     * @param sourceArray 待排序数组
     * @param order 排序方式，(默认)升序 true；降序 false
     * @return 排序后的数组
     * @throws Exception 异常信息
     */
    public abstract Integer[] sort(Integer[] sourceArray,Boolean order) throws Exception;

    /**
     * 通过 位运算 进行数字交换
     * @param arr 待处理的数组
     * @param index1 待交换数据的下标1
     * @param index2 待交换数据的下标2
     */
    protected static void swapValBit(Integer[] arr,int index1,int index2){
        ArrayTool.swapValBit(arr, index1, index2);
    }
    /**
     * 通过 加减运算 进行数字交换
     * @param arr 待处理的数组
     * @param index1 待交换数据的下标1
     * @param index2 待交换数据的下标2
     */
    protected static void swapValArithmetic(Integer[] arr,int index1,int index2){
        if(index1 == index2 || arr[index1].equals(arr[index2])) { return; }
        arr[index1] = arr[index1] + arr[index2];
        arr[index2] = arr[index1] - arr[index2];
        arr[index1] = arr[index1] - arr[index2];
    }
    /**
     * 通过 临时变量 进行数字交换
     * @param arr 待处理的数组
     * @param index1 待交换数据的下标1
     * @param index2 待交换数据的下标2
     */
    protected static void swapVal(Integer[] arr,int index1,int index2){
        ArrayTool.swapVal(arr, index1, index2);
    }
    /**
     * 排序函数统计开始
     */
    protected static void start(){
        count = new AtomicInteger();
        startTime = System.nanoTime();
    }
    /**
     * 排序函数统计结束并输出
     */
    protected static void end(){
        long runTime = System.nanoTime()-startTime;
        System.out.print("运行耗时:"+ DateTool.longFormatByNanoTime(runTime));
        System.out.println("，有效迭代/循环次数:"+count);
    }
    /**
     * 统计迭代/循环次数增加1
     */
    protected static void addOne(){
        count.incrementAndGet();
    }
    /**
     * 控制台打印数组
     * @param arr 数组
     */
    protected static void printArray(Integer[] arr){
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 对 数组 进行拷贝，不改变参数内容
     * @param arr 原数组
     * @return 复制的数组
     */
    protected static Integer[] copyArray(Integer[] arr){
        return copyArray(arr, arr.length);
    }
    /**
     * 对 数组 进行拷贝，不改变参数内容
     * @param arr 原数组
     * @param len 原数组长度
     * @return 复制的数组
     */
    protected static Integer[] copyArray(Integer[] arr,int len){
        System.out.print("arr：");
        printArray(arr);
        return Arrays.copyOf(arr, len);
    }

    /**
     * 随机数组生成(可能存在重复数据)，最小值0
     * <p>可能存在重复数据，最小值0</p>
     * @param len 数组长度
     * @param max 最大值
     * @return 随机数组
     */
    protected static Integer[] randomArray(int len,int max){
        RANDOM.setSeed(System.nanoTime());
        Integer[] arr = new Integer[len];
        for (int i = 0; i < len; i++) {
            //替代 Math.random()方法
            arr[i] = RANDOM.nextInt(max);
        }
        return arr;
    }
    /**
     * 随机指定范围内N个不重复的数
     * <p>双层for循环，性能差</p>
     * <p>min和max差距太小，会造成随机数重复率过高</p>
     * <p>最简单最易理解的两重循环去重</p>
     * @param min 指定范围最小值
     * @param max 指定范围最大值
     * @param size 随机数个数,数组长度
     */
    protected static Integer[] randomArrayByFor(int min, int max, int size){
        if (size > (max - min + N_1) || max < min) { return null; }
        Integer[] result = new Integer[size];
        int num;
        boolean flag = true;
        RANDOM.setSeed(System.nanoTime());
        for (int i = N_0; i < size; ) {
            num = RANDOM.nextInt(max) + min;
            for (int j = N_0; j < size; j++) {
                //如果类型为int，可以去掉null验证，Integer不能
                if(null == result[j]){result[j]=NE_1;}
                if(num == result[j]){
                    flag = false;
                    break;
                }
            }
            if(flag){
                result[i] = num;
                i++;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int len =10,max=150,index1=0,index2=1,min=5;
        Integer[] arr = randomArray(len, max);
        printArray(arr);
        swapVal(arr, index1, index2);
        printArray(arr);
        index1=2;index2=4;
        swapValBit(arr,  index1, index2);
        printArray(arr);
        index1=3;index2=1;
        swapValArithmetic(arr,  index1, index2);
        printArray(arr);
        System.out.println("随机数组（含重复数）-使用Stream流的方式生成");
        printArray(ArrayTool.randomArrayByStream(len ,max));
        System.out.println("随机数组（排重-适合min和max的差值远远大于len）-利用HashSet的特征，只能存放不同的值，单层for循环");
        printArray(ArrayTool.randomArrayBySet(min,max,len));
        System.out.println("随机数组（排重-适合min和max的差值大于等于len）-利用待选数组选取随机下标，两个for循环");
        printArray(ArrayTool.randomArrayByIndex(min,max,len));
        System.out.println("随机数组（排重-性能最差）-最简单最易理解的两重循环去重");
        printArray(randomArrayByFor(min,max,len));
    }
}